Very sparse stable random projections for dimension reduction in <i>l</i>&#945; (0 &#60;&#945; &#8804; 2) norm
Ping Li
The method of <i>stable random projections</i> is a useful tool for efficiently computing the <i>l</i>&#945; (0 < &#945; &#8804; 2) norms and distances in massive data in one pass. Consider a data matrix <b>A</b> &#8712;R<sup><i>nxD</i></sup>. If we multiply <b>A</b> with a projection matrix <b>R</b> &#917;R <sup><i>Dxk</i></sup> (<i>k</i>&#171; <i>D</i>),whose entries are i.i.d. samples of an &#945;-stable distribution,then the projected matrix <b>B</b> = <b>A</b>x <b>R</b> &#917; <b>R</b> <sup><i>nxk</i></sup>x containsenough information to approximately recover the <i>l</i> &#945; properties in <b>A</b>.</p> <p>We propose <i>very sparse stable random projections</i>, by replacing the &#945; stable distribution with a (much simpler) mixture of a symmetric &#945; Pareto distribution (with probability &#914;, 0 &#946; &#914; 1) and a point mass at the origin(with probability 1-&#914;). This leads to a significant 1 over &#914; fold speedup for small &#914; when computing <b>B</b> = <b>A</b>x<b>R</b> and a 1 over &#914;-fold cost reduction in storing <b>R}</b>. By analyzing the convergence, we show that in"reasonable" datasets &#914; often can be very small (e.g.,<i>D</i><sup>1/2</sup> without hurting the estimation accuracy. Some numerical evaluations are conducted, on synthetic data, Web crawldata, and gene expression microarray data.
